\subsubsection{Solución elegida}

Como dijimos anteriormente, la idea es barrer los puntos de izquierda a derecha armando, con cada uno de ellos, todas las cajas determinadas por éstos y los puntos que estuvieren ``por debajo'' y ``a su derecha'' (incluído él mismo). Para cada una de estas cajas, calculamos la cantidad de puntos de $C$ que contiene y nos vamos quedando con la que contenga más de ellos.

\subsubsection{Justificación}

Como vimos antes, dado un ``cuadrado óptimo'', es posible obtener otro (o el mismo) ``moviendo'' el primero hacia la derecha y hacia arriba hasta que ocurra alguna de las siguientes cosas:

\begin{itemize}
	\item Que uno o más de los puntos del cuadrado original esté ``tocando'' la base del nuevo cuadrado y otro u otros de ellos estén ``tocando'' el lado izquierdo del cuadrado. Este caso ocurriría si dos puntos diferentes tuvieran uno el mínimo $X$ y otro el mínimo $Y$ entre los puntos incluídos en el ``cuadrado óptimo''.
	\item Que uno de los puntos quede en el vértice. Este caso ocurriría si un solo punto tuviera tanto el mínimo $X$ como el mínimo $Y$ entre los puntos incluídos en el ``cuadrado óptimo''.
\end{itemize}

A partir de esto, podemos concluír que siempre existe un ``cuadrado óptimo'' tal que alguno de los puntos que contiene está justo sobre su lado izquierdo y algún otro (o el mismo) está justo sobre su base. Así, alcanza con analizar cuántos puntos encierran los cuadrados que cumplen esta premisa.

\subsubsection{Pseudocódigo}

El tipo $Punto$ es $Tupla \langle Int, Int \rangle$, donde $Punto.Primero$ representa la coordenada $X$ del mismo y $Punto.Segundo$ la coordenada $Y$. Para que el pseudocódigo sea más declarativo, utilizaremos la notación $Punto.X$ para la coordenada $X$ y $Punto.Y$ para la coordenada $Y$.

El tipo $Cuadrado$ es $Tupla \langle Int, Int, Int, Int \rangle$ donde, en orden, las componentes indican coordenadas $X$ e $Y$ del vértice inferior izquierdo, la base y la altura del mismo.

\begin{pseudocode}[ruled]{HallarCajaOptima}{Secuencia\langle Punto\rangle \; puntos, Int \; base, Int \; altura}

	\LOCAL puntosOrdenados \GETS \CALL{Sort}{puntos, \CALL{CompararPorX}} \\
	\LOCAL cuadradoOptimo \GETS \langle 0, 0, base, altura \rangle \\
	\LOCAL puntosEnOptimo \GETS \CALL{PuntosIncluidos}{puntos, cuadradoOptimo} \\ \\

	\FOR i \GETS 0 \TO Tamanio(puntos) - 1 \\ \DO
	\BEGIN
		\LOCAL pivote \GETS puntosOrdenados[i] \\
		\FOR j \GETS i \TO Tamanio(puntos) - 1 \\ \DO
		\BEGIN
			\IF puntosOrdenados[j].Y > pivote.Y \THEN
				\textbf{continue} \\ \\
			\LOCAL cuadradoCandidato \GETS \\ \CALL{CuadradoDefinidoPor}{pivote, puntosOrdenados[j], base, altura} \\
			\LOCAL puntosEnCandidato \GETS \CALL{PuntosIncluidos}{puntos, cuadradoCandidato} \\ \\
			\IF (puntosEnCandidato \leq puntosEnOptimo) \THEN
				\textbf{continue} \\ \\
			cuadradoOptimo \GETS cuadradoCandidato \\
			puntosEnOptimo \GETS puntosEnCandidato \\
		\END \\
		
	\END \\ \\
	
	\OUTPUT{cuadradoOptimo, puntosEnOptimo}

\end{pseudocode}

\begin{pseudocode}[ruled]{CompararPorX}{Punto \; punto1, Punto \; punto2}

	\LOCAL result \GETS punto1.X < punto2.X \\ \\
	\RETURN {result}

\end{pseudocode}

\begin{pseudocode}[ruled]{CuadradoDefinidoPor}{Punto \; punto1, Punto \; punto2, Int \; base, Int \; altura}

	\LOCAL cuadrado \GETS \langle punto1.X, punto2.Y, base, altura \rangle \\ \\
	\RETURN {cuadrado}

\end{pseudocode}

\begin{pseudocode}[ruled]{PuntosIncluidos}{Secuencia\langle Punto\rangle \; puntos, Cuadrado \; cuadrado}

	\LOCAL result \GETS 0 \\
	\FOREACH punto \in puntos \DO
		\BEGIN
			\IF cuadrado.X \leq punto.X \leq cuadrado.X + cuadrado.Base \\
				\AND cuadrado.Y \leq punto.Y \leq cuadrado.Y + cuadrado.Altura
				\THEN
				result \GETS result + 1 \\
		\END \\ \\
	
	\RETURN {result}

\end{pseudocode}

%\begin{comment0}
%xyp resolver(int& k, int& base, int& altura, vector<int>& vx, vector<int>& vy, vector<pair<int,int> >& puntos){
%	xyp res;
%	res.second = 0;
%
%	mergesortX(puntos,0,k-1);//ordeno los puntos por la primer coordenada
%
%	int minX = 0;
%	int minY = 0;
%	int max = 0;
%
%	for(int i = 0; i<k; i++){ //lamemos a este elemento A
%		int tmpMinX = 0;
%		int tmpMinY = 0;
%
%
%		for(int j = 0; j<k; j++){ // Tomo otro elemento B que este en el cuadrado de A sumando o restando altura
%			if( (i>=j)&&( puntos[i].first + base >= puntos[j].first) &&
%			   ( puntos[i].second + altura >= puntos[j].second ||
%			     puntos[i].second - altura <= puntos[j].second
%			     )  ){
%
%				//Agarro 2 puntos en el plano si estan a distancia B me quedo con el menor X y el menor Y
%				if(puntos[i].first > puntos[j].first){
%					tmpMinX = puntos[j].first;
%				}else{
%					tmpMinX = puntos[i].first;
%				}
%
%				if(puntos[i].second > puntos[j].second){
%					tmpMinY = puntos[j].second;
%				}else{
%					tmpMinY = puntos[i].second;
%				}
%				int tmpMaxUp = 0;
%				int tmpMaxDown = 0;
%
%				for(int m = 0; m<k;m++){ //Me fijo entre A y B que elementos comparten.
%						if(tmpMinX + base >= puntos[m].first){
%
%							if  ( tmpMinY + altura >= puntos[m].second ){
%								tmpMaxUp++;
%							} else if ( tmpMinY - altura >= puntos[m].second){
%								tmpMaxDown++;
%							}
%
%						}
%				}
%
%				if (tmpMaxDown < tmpMaxUp){
%					if(max<tmpMaxUp){
%						max = tmpMaxUp;
%						minX = tmpMinX;
%						minY = tmpMinY;
%					}
%				}else{
%					if(max<tmpMaxDown){
%						max = tmpMaxDown;
%						minX = tmpMinX;
%						minY = tmpMinY;
%					}
%				}
%			}
%	}
%	res.second = max;
%	res.first.first = minX;
%	res.first.second = minY;
%	return res;
%	}
%
%}
%
%
%
%void mergeX(vector<pair<int,int> >& arr, int m, int l, int n){
%	vector<pair<int,int> > res;
%	int a,s;
%	a= m;
%	s= l+1;
%
%	int pivot = l;
%	while(a<=pivot && s<=n){
%		if (arr[a].first > arr[s].first){
%			res.push_back(arr[s]);
%			s++;
%		}else{
%			res.push_back(arr[a]);
%			a++;
%		}
%	}
%
%		for(int i= a ; i<=pivot ;i++){
%			res.push_back(arr[i]);}
%
%		for(int i= s ; i<=n ;i++){
%			res.push_back(arr[i]);}
%    int p = 0;
%	for(int k = m; k<=n ; k++){
%	    arr[k]=res[p];
%	    p++;
%
%	}
%
%}
%
%
%
%
%void mergesortX(vector<pair<int,int> >& a,int m, int n){
%        if( n-m == 1 && a[m].first>a[n].first ){
%                pair<int,int> temp = a[m];
%                a[m] =  a[n];
%                a[n] =  temp;
%
%        }else if(n-m>1){
%		int l = (n-m)/2;
%		mergesortX(a,m,m+l);
%		mergesortX(a,m+l+1,n);
%		mergeX( a,m,m+l,n);
%
%
%	}
%}
%
%\end{comment}

